#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <vector>

using namespace std;
using LL = long long;
const int N = 1e6 + 10;

int n, m;
int x[N], y[N], c[N], sa[N], rk[N], height[N];
char s[N];

void get_sa(){
    for(int i = 1; i <= n; i ++) c[x[i] = s[i]] ++;
    for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
    for(int i = n; i; i--) sa[c[x[i]] --] = i;

    for(int k = 1; k <= n; k <<= 1){
        int num = 0;

        for(int i = n - k + 1; i <= n; i ++){
            y[++num] = i;
        }

        for(int i = 1; i <= n; i ++){
            if(sa[i] > k){
                y[++num] = sa[i] - k;
            }
        }

        for(int i = 1; i <= m; i ++) c[i] = 0;
        for(int i = 1; i <= n; i ++) c[x[i]] ++;
        for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
        for(int i = n; i; i --) sa[c[x[y[i]]] --] = y[i], y[i] = 0;
        swap(x, y);

        x[sa[1]] = 1, num = 1;
        for(int i = 2; i <= n; i ++){
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
        }
        if(num == n) break;
        m = num;
    }
}

void get_height(){
    for(int i = 1; i <= n; i ++) rk[sa[i]] = i;

    for(int i = 1, k = 0; i <= n; i ++){
        if(rk[i] == 1) continue;

        if(k) k --;
        int j = sa[rk[i] - 1];
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++;
        height[rk[i]] = k;
    }
}

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s + 1;
    n = strlen(s + 1), m = 122;

    get_sa();
    get_height();

    for(int i = 1; i <= n; i ++) cout << sa[i] << " ";
    cout << '\n';
    for(int i = 1; i <= n; i ++) cout << height[i] << " ";
    cout << '\n';

    return 0;
}